See chromatic number on Wiktionary
{
"forms": [
{
"form": "chromatic numbers",
"tags": [
"plural"
]
}
],
"head_templates": [
{
"args": {},
"expansion": "chromatic number (plural chromatic numbers)",
"name": "en-noun"
}
],
"lang": "English",
"lang_code": "en",
"pos": "noun",
"senses": [
{
"categories": [
{
"kind": "other",
"name": "English entries with incorrect language header",
"parents": [
"Entries with incorrect language header",
"Entry maintenance"
],
"source": "w"
},
{
"kind": "other",
"name": "Entries with translation boxes",
"parents": [],
"source": "w"
},
{
"kind": "other",
"name": "Pages with 1 entry",
"parents": [],
"source": "w"
},
{
"kind": "other",
"name": "Pages with entries",
"parents": [],
"source": "w"
},
{
"kind": "other",
"name": "Terms with Hungarian translations",
"parents": [],
"source": "w"
},
{
"kind": "other",
"name": "Terms with Icelandic translations",
"parents": [],
"source": "w"
},
{
"kind": "other",
"name": "Terms with Italian translations",
"parents": [],
"source": "w"
},
{
"kind": "other",
"name": "Terms with Spanish translations",
"parents": [],
"source": "w"
},
{
"kind": "topical",
"langcode": "en",
"name": "Graph theory",
"orig": "en:Graph theory",
"parents": [
"Mathematics",
"Visualization",
"Formal sciences",
"Computing",
"Interdisciplinary fields",
"Sciences",
"Technology",
"All topics",
"Fundamental"
],
"source": "w"
}
],
"derived": [
{
"word": "chromatic number problem"
},
{
"word": "edge chromatic number"
},
{
"word": "harmonious chromatic number"
},
{
"word": "total chromatic number"
}
],
"examples": [
{
"text": "The chromatic number of a complete graph K#x5F;n is n; the chromatic number of a bipartite graph K#x5F;#x7B;n,m#x7D; is 2.",
"type": "example"
},
{
"ref": "1995, J. A. Bondy, “1: Basic Graph Theory: Paths and Circuits”, in Ronald L. Graham, Martin Grötschel, László Lovász, editors, Handbook of Combinatorics, Volume 1, Elsevier (North-Holland), page 48:",
"text": "The chromatic number of a graph G is the minimum value of k for which G is k-colourable, and is denoted by #x5C;chi(G).[…]A more essential use of the chromatic number was made by Gallai (1968a) and Roy (1967), who discovered a simple relationship between the chromatic number of a digraph and the length of a longest directed path in the digraph, where the chromatic number #x5C;chi(D) of a digraph D is defined to be the chromatic number of its underlying graph G(D).",
"type": "quote"
},
{
"text": "2004, Monia Discepoli, Ivan Gerace, Riccardo Mariani, Andrea Remigi, A Spectral Technique to Solve the Chromatic Number Problem in Circulant Graphs, Antonio Laganà, et al. (editors), Computational Science and Its Applications, ICCSA 2004: International Conference, Proceedings, Part 3, Springer, LNCS 3045, page 745,\nThe CHROMATIC NUMBER is the minimum number of colors by means of which it is possible to color a graph in such a way that each vertex has a different color with respect to the adjacent vertices. Such a problem is an NP-hard problem [14] and [it] is even hard to obtain a good approximation of the solution in a polynomial time [17]. Although in a lot of computational problems the cost decreases when these problems are restricted to circulant graphs [6, 9], the CHROMATIC NUMBER problem is NP-hard even restrecting to circulant graphs [9]. Moreover the problem of finding a good approximation of the CHROMATIC NUMBER problem on circulant graphs is also NP-hard."
},
{
"text": "2009, Gary Chartrand, Ping Zhang, Chromatic Graph Theory, Taylor & Francis Group (CRC Press / Chapman & Hall), page 149,\nThere is no general formula for the chromatic number of a graph. Consequently, we will often be concerned and must be content with (1) determining the chromatic number of some classes of interest and (2) determining upper and/or lower bounds for the chromatic number of a graph."
}
],
"glosses": [
"The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
],
"id": "en-chromatic_number-en-noun-bT27JdHm",
"links": [
[
"graph theory",
"graph theory"
],
[
"colour",
"colour"
],
[
"graph",
"graph"
],
[
"vertex",
"vertex"
],
[
"edge",
"edge"
]
],
"raw_glosses": [
"(graph theory) The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
],
"related": [
{
"word": "achromatic number"
},
{
"word": "chromatic index"
},
{
"word": "chromatic polynomial"
},
{
"word": "k-colouring"
},
{
"word": "k-chromatic"
}
],
"synonyms": [
{
"english": "used to differentiate from edge chromatic number",
"sense": "smallest number of colours needed to colour the vertices of a graph",
"tags": [
"usually"
],
"word": "vertex chromatic number"
}
],
"topics": [
"graph-theory",
"mathematics",
"sciences"
],
"translations": [
{
"code": "hu",
"lang": "Hungarian",
"sense": "smallest number of colours needed to colour a graph",
"word": "kromatikus szám"
},
{
"code": "is",
"lang": "Icelandic",
"sense": "smallest number of colours needed to colour a graph",
"tags": [
"feminine"
],
"word": "litatala"
},
{
"code": "it",
"lang": "Italian",
"sense": "smallest number of colours needed to colour a graph",
"tags": [
"masculine"
],
"word": "numero cromatico"
},
{
"code": "es",
"lang": "Spanish",
"sense": "smallest number of colours needed to colour a graph",
"tags": [
"masculine"
],
"word": "número cromático"
}
]
}
],
"word": "chromatic number"
}
{
"derived": [
{
"word": "chromatic number problem"
},
{
"word": "edge chromatic number"
},
{
"word": "harmonious chromatic number"
},
{
"word": "total chromatic number"
}
],
"forms": [
{
"form": "chromatic numbers",
"tags": [
"plural"
]
}
],
"head_templates": [
{
"args": {},
"expansion": "chromatic number (plural chromatic numbers)",
"name": "en-noun"
}
],
"lang": "English",
"lang_code": "en",
"pos": "noun",
"related": [
{
"word": "achromatic number"
},
{
"word": "chromatic index"
},
{
"word": "chromatic polynomial"
},
{
"word": "k-colouring"
},
{
"word": "k-chromatic"
}
],
"senses": [
{
"categories": [
"English countable nouns",
"English entries with incorrect language header",
"English lemmas",
"English multiword terms",
"English nouns",
"English terms with quotations",
"English terms with usage examples",
"Entries with translation boxes",
"Pages with 1 entry",
"Pages with entries",
"Terms with Hungarian translations",
"Terms with Icelandic translations",
"Terms with Italian translations",
"Terms with Spanish translations",
"en:Graph theory"
],
"examples": [
{
"text": "The chromatic number of a complete graph K#x5F;n is n; the chromatic number of a bipartite graph K#x5F;#x7B;n,m#x7D; is 2.",
"type": "example"
},
{
"ref": "1995, J. A. Bondy, “1: Basic Graph Theory: Paths and Circuits”, in Ronald L. Graham, Martin Grötschel, László Lovász, editors, Handbook of Combinatorics, Volume 1, Elsevier (North-Holland), page 48:",
"text": "The chromatic number of a graph G is the minimum value of k for which G is k-colourable, and is denoted by #x5C;chi(G).[…]A more essential use of the chromatic number was made by Gallai (1968a) and Roy (1967), who discovered a simple relationship between the chromatic number of a digraph and the length of a longest directed path in the digraph, where the chromatic number #x5C;chi(D) of a digraph D is defined to be the chromatic number of its underlying graph G(D).",
"type": "quote"
},
{
"text": "2004, Monia Discepoli, Ivan Gerace, Riccardo Mariani, Andrea Remigi, A Spectral Technique to Solve the Chromatic Number Problem in Circulant Graphs, Antonio Laganà, et al. (editors), Computational Science and Its Applications, ICCSA 2004: International Conference, Proceedings, Part 3, Springer, LNCS 3045, page 745,\nThe CHROMATIC NUMBER is the minimum number of colors by means of which it is possible to color a graph in such a way that each vertex has a different color with respect to the adjacent vertices. Such a problem is an NP-hard problem [14] and [it] is even hard to obtain a good approximation of the solution in a polynomial time [17]. Although in a lot of computational problems the cost decreases when these problems are restricted to circulant graphs [6, 9], the CHROMATIC NUMBER problem is NP-hard even restrecting to circulant graphs [9]. Moreover the problem of finding a good approximation of the CHROMATIC NUMBER problem on circulant graphs is also NP-hard."
},
{
"text": "2009, Gary Chartrand, Ping Zhang, Chromatic Graph Theory, Taylor & Francis Group (CRC Press / Chapman & Hall), page 149,\nThere is no general formula for the chromatic number of a graph. Consequently, we will often be concerned and must be content with (1) determining the chromatic number of some classes of interest and (2) determining upper and/or lower bounds for the chromatic number of a graph."
}
],
"glosses": [
"The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
],
"links": [
[
"graph theory",
"graph theory"
],
[
"colour",
"colour"
],
[
"graph",
"graph"
],
[
"vertex",
"vertex"
],
[
"edge",
"edge"
]
],
"raw_glosses": [
"(graph theory) The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
],
"topics": [
"graph-theory",
"mathematics",
"sciences"
]
}
],
"synonyms": [
{
"english": "used to differentiate from edge chromatic number",
"sense": "smallest number of colours needed to colour the vertices of a graph",
"tags": [
"usually"
],
"word": "vertex chromatic number"
}
],
"translations": [
{
"code": "hu",
"lang": "Hungarian",
"sense": "smallest number of colours needed to colour a graph",
"word": "kromatikus szám"
},
{
"code": "is",
"lang": "Icelandic",
"sense": "smallest number of colours needed to colour a graph",
"tags": [
"feminine"
],
"word": "litatala"
},
{
"code": "it",
"lang": "Italian",
"sense": "smallest number of colours needed to colour a graph",
"tags": [
"masculine"
],
"word": "numero cromatico"
},
{
"code": "es",
"lang": "Spanish",
"sense": "smallest number of colours needed to colour a graph",
"tags": [
"masculine"
],
"word": "número cromático"
}
],
"word": "chromatic number"
}
Download raw JSONL data for chromatic number meaning in All languages combined (4.6kB)
This page is a part of the kaikki.org machine-readable All languages combined dictionary. This dictionary is based on structured data extracted on 2024-11-06 from the enwiktionary dump dated 2024-10-02 using wiktextract (fbeafe8 and 7f03c9b). The data shown on this site has been post-processed and various details (e.g., extra categories) removed, some information disambiguated, and additional data merged from other sources. See the raw data download page for the unprocessed wiktextract data.
If you use this data in academic research, please cite Tatu Ylonen: Wiktextract: Wiktionary as Machine-Readable Structured Data, Proceedings of the 13th Conference on Language Resources and Evaluation (LREC), pp. 1317-1325, Marseille, 20-25 June 2022. Linking to the relevant page(s) under https://kaikki.org would also be greatly appreciated.